package chapter01.problem07;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
 * 生成窗口最大值数组
 */
public class Pronlem07 {

	/**
	 * 生成窗口最大值数组
	 * @param a			目标数组
	 * @param win_size	窗口大小
	 * @return	每一种窗口下的最大数组
	 */
	public static int[] getMaxInWindow(int[] a , int win_size){
		int len = a.length;
		if(len < win_size)	//如果窗口大小大于数组的大小，则直接返回(PS.是直接返回a中的最大值呢，还是抛异常呢？？？)
			throw new IllegalArgumentException("目标数组长度小于窗口大小！");
		int[] result=new int[len-win_size+1];
		//使用双端队列来保存窗口最大值的更新，其中队列头保存的是当前窗口的最大值
		//双端队列中保存的是下标，不过后面为了简便叙述，直接说是双端队列中的值与数组中的值进行比较
		List<Integer> list = new LinkedList<Integer>();
		for(int i = 0; i < len; ++i){
			//如果窗口已经过了队列中的最大值的下标，则从窗口中移除
			if(!list.isEmpty() && i - list.get(0)+1 > win_size)
				list.remove(0);
			while(!list.isEmpty()){
				//如果双端队列最后的元素小于当前元素，则从双端队列中移除，并循环操作
				if(a[list.get(list.size()-1)] < a[i]){
					list.remove(list.size()-1);
				}else{//如果双端队列最后的元素大于当前元素，则直接将当前元素添加进双端队列中
					list.add(i);
					break;
				}
			}//如果双端队列为空，则直接添加
			if(list.isEmpty())
				list.add(i);
			//如果已经满足窗口的大小，则开始往结果数组中赋值
			if(i>=win_size-1)
				result[i-win_size+1]=a[list.get(0)];
		}
		
		return result;
	}
	/**
	 * 测试
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = {4,3,5,4,3,3,6,7};
		int win_size=3;
		int[] result = Pronlem07.getMaxInWindow(a, win_size);
		System.out.println(Arrays.toString(result));
	}
}
